In the field of packet-switched communications, content conveyed between a source network node and a destination network node participating in a communications network, is segmented for transport in packets. Packets have a structure including a packet header and a content payload. Communications network nodes in the path between the source and destination network nodes, such as, but not limited to, switching network nodes, receive, store, inspect, process, and forward each packet based on information specified in the packet header. This mode of operation is know as non-deterministic store-and-forward packet-switching.
Switching network nodes are multiported network nodes. Processing each stored packet received via an input port includes determining at least one output port via which to forward the stored packet. The determination of the at least one output port coupled with actual forwarding via the at least one determined output port is know as packet switching. An important characteristic of a generic switching network node, and a requirement of a switching network node employed in the core of a communications network, is that, output bandwidth permitting, store-and-forward packet-switching be performed at incoming line/wire speed on an ongoing basis. While such a requirement seems reasonable, in practice it is difficult to achieve in spite of, and because of, numerous recent advances in the field.
The history and development of packet-switched communications is very diverse including: the use of multiple technologies to at the physical Layer-1 such as: wired, wireless, optical physical transport etc.; the use of multiple encapsulation technologies at the data-link Layer-2 including Ethernet technologies; the use of multiple transport protocols at the network Layer-3 including the Internet Protocol (IP), Internet Control Message Protocol (ICMP), etc. The IP-over-Ethernet technologies enjoy the widest deployment.
For example, standard IP/Ethernet provides non-deterministic best-effort packet transport. The non-deterministic characteristics provide for autonomous re-routing of packets around failed communications network infrastructure, however the best-effort characteristic does not provide guarantees regarding successful (not even untimely) packet transport between the source and destination network node. A Transport Control Protocol (TCP) is further employed to identify missing packets providing the means for requesting retransmission thereof. Timely packet transport is addressed via traffic/service differentiation and provided through preferential packet processing at intermediary communications network nodes between the source and destination network nodes.
It is difficult to address all of the above issues in providing sustained packet-switching at wire/line speed. While theoretical developments in this regard provide assurances that such switching network nodes could be constructed, practical implementations are mired with high development, implementation, and validation costs, as well suffer from various implementation complexities. Due to a rapid development in the field, not only are switching network nodes required to operate at line/wire speed while processing multi-protocol minimum length packets, also a measure of flexibility is desired to delay equipment obsolesce in view of future technology developments:
In prior art United States Patent Application publication No. 2002/54604 A1 entitled “Network Switching Architecture with Fast Filtering Processor” which became available to the public on May 9, 2002, Kadambi et al. describe a method and apparatus for filtering packets received via an input port. Packet processing culminating in a decision whether to discard a packet, is know as packet filtering. While Kadambi et al. teach implementation of switching network node functions on a single chip wherein switching node functions are modularized for independent development, the implementation described is complex and cumbersome as, filtering implemented in respect of each port requires a complex arbitrated group of three channels providing internal communication between the port modules. Packet filtering on its own does not switch packets, only provides the means to reduce unnecessary packet processing. Some security aspects are also addressed through packet filtering which further points to the importance of packet filtering. While port based filtering may very well provide packet filtering at line/wire speed, filtering alone does not address the other above mentioned issues regarding packet processing at a switching network node.
Co-assigned U.S. Pat. No. 6,697,873 B1 entitled “High Speed MAC Address Search Engine” issued Feb. 24, 2004 to Yik et al. (some of which are named inventors herein) and incorporated herein by reference, describes an apparatus and method for storing and searching network node addresses in a communications network node, such as a switching network node. The apparatus includes two Media Access Control (MAC) address tables for storing and searching MAC addresses. A primary MAC Address table stores records specifying compressed values corresponding to MAC addresses, and each record is stored at storage a location referenced using the hashed MAC address value as an index. In order to account for search collisions that may result from multiple MAC addresses hashing to the same index, and therefore to the same location in the primary MAC address table, each record in the primary MAC address table is further linked to a corresponding chain of records stored in the secondary MAC address table. Records in the secondary MAC address table specify full MAC addresses. MAC address storage at switching network nodes is important in reducing the processing required in switching packets: records in the MAC address tables also include previously determined output ports for similarly addressed packets. Fast retrieval of MAC address records from the MAC address tables is important in achieving fast packet switching. The implementation described by Yik et al. provides a balance between cost of implementing MAC address lookups and the speed of the MAC address search.
Co-pending co-assigned U.S. patent application Ser. No. 10/750,445 entitled “High Speed MAC Address Search Engine” filed Dec. 31, 2003 by Barrak et al. (some of which are inventors named herein) and incorporated herein by reference, describes an improved apparatus and methods for storing and searching network node addresses in a communications network node such as a switching network node. The apparatus includes two Media Access Control (MAC) address tables for storing and searching MAC addresses. A primary MAC address table, external to the packet switching processor, stores records specifying compressed values corresponding to MAC addresses, more than one record being stored at storage locations referenced using hashed MAC address values as indicia. External storage of the primary MAC address table enables the use off the shelf memories providing ample storage which is balanced against a data transfer overhead between the switching processor and the external memory. In order to account for search collisions that may result from multiple MAC addresses hashing to the same index, each record in the primary MAC address table is further linked to corresponding chains of records stored in the secondary MAC address table. Records in the secondary MAC address table specifies compressed MAC addresses to minimize secondary MAC address table storage requirements particularly as the secondary MAC address table is implemented on the same microchip die with the packet switching processor.
While the above described developments towards improved switching performance have made great strides, there still is a need to address the above mentioned issues in further improving switching performance particularly in support of higher port densities.